package day22;

/**
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 *
 * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 1, a = 2, b = 3
 * 输出：2
 * 示例 2：
 *
 * 输入：n = 4, a = 2, b = 3
 * 输出：6
 */
public class Solution1 {
    public int nthMagicalNumber(int n, int a, int b) {
        int mod = 1000000007;
        long left = 0,right = (long)Math.max(a,b)*n;
        long lcm = (a*b)/gcd(a,b);
        while (left+1<right){
            long mid = (right-left)/2+left;
            if(mid/a+mid/b-mid/lcm>=n){
                right = mid;
            }else{
                left = mid;
            }
        }
        return (int) (right%mod);
    }
    public int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}
